As is known in the art, packet-based communication systems include a series of interconnected devices, such as routers, for enabling point-to-point data exchanges. The failure of network elements and/or traffic surges can cause packet routers to receive traffic at a higher rate than the bandwidth of the link on the output interface to which the traffic is routed. This can result in the build-up of packets in a buffer contained in the router. If the overload condition persists long enough, the buffer can overflow and degrade end-user performance.
So-called overload controls can be used to selectively discard packets so that the “most important” packets are delivered to the extent possible. Two examples of most important packets are those containing network control information and those from end-users who pay a premium for special treatment.
Quality of service (QoS) differentiation of packets is the basis for several known packet-network services. In typical QoS schemes, packets are marked according to their class of service (which is a measure of “value”). An overflow control algorithm uses this information to discard the “least valuable packets” first. It may be desirable to avoid discarding all of the least valuable packets in order to retain end user goodwill. The capability of current routers to maintain throughput-by-class under overload is primarily provided in an algorithm called weighted random early discard (WRED).
However, there are drawbacks to using the WRED algorithm for overload control. More particularly, when WRED is configured to ensure that the most valuable packets are protected from being discarded in the case where the overload is caused by an excess of low-value packets, the low-value packets receive an undesirably small throughput when the overload is caused by high-value packets. That is, class 1 traffic is protected from class 2 overloads but class 2 traffic is not protected from class 1 overloads. While so-called smoothing may avoid preventive discards on small traffic bursts, WRED does not avoid them when the queue empties after a large burst. Further, probabilistic dropping in WRED, which is designed to avoid consecutive packet drops from the same end user, is not needed on backbone routers since these routers serve a relatively large number of users. In addition, the performance of WRED is not easily predicted, so that setting the control parameters to achieve performance objectives is challenging.
Additional known active queue management ways of providing preferential services by class when packets are placed in a single queue include priority queuing (PQ) and Weighted Fair Queuing (WFQ). Deficit Round Robin (DRR) is a scheduling algorithm that provides preferential service by class when packets from different classes are placed in separate queues. However, priority queuing cannot provide bandwidth guarantees to all classes. While Weighted Fair Queuing provides bandwidth guarantees to all classes by controlling the packet processing schedule, its computational requirements grow with the number of connections so it may not scale to backbone routers, which handle a very large number of connections. And Deficit Round Robin applies to router architectures that place packets from different classes into different queues, so it cannot be used in routers with a single queue for all packets. Another scheduling algorithm is described in Clark and Fang, “Explicit Allocation of Best-Effort Packet Delivery Service,” IEEE/ACM Transactions on Networking, Vol. 6, No. 4, August 1998, which is incorporated herein by reference.
These existing overload control algorithms provide only limited levels of performance and do not enable users to configure routers to achieve the limited performance levels with adequate reliability. Without such reliability, systems designers cannot accurately predict the effects of overloads on end-users.
It would, therefore, be desirable to provide a reliable packet-based communication system having enhanced overload performance.